package debtbundler.domain.bll.solver;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

import debtbundler.domain.entity.Debt;
import debtbundler.domain.entity.Person;
import debtbundler.domain.entity.impl.EntityManager;

/**
 * A solver that minimizes the number of debts by settling debts in all possible
 * combinations such that the maximum value is always settled between a debtor-creditor
 * pair.
 * 
 * @author Anssi
 *
 */
public class AllCombinationsSolver extends SolverSkeleton {
	private static Logger logger = Logger.getLogger(AllCombinationsSolver.class.getName());
	
	/** Debts calculated at the current search step  */
	private Set<Debt> currentDebts;
	// The best solution is stored in super.debts 
	
	public AllCombinationsSolver(Collection<Person> persons) {
		solve(persons);
	}

	@Override
	protected void calculateSolution() {
		this.debts = null; // nullify for search to know if no debts yet calculated
		currentDebts = new HashSet<Debt>();
		search(new ArrayList<Person>(debtors), new ArrayList<Person>(creditors));
		
		if (debts == null) {
			debts = new ArrayList<Debt>(); 
		}
		for (Debt debt : debts) {
			debt.getDebtor().addDebt(debt);
		}
	}
	
	/**
	 * Traverse the search tree. After the search is complete, the best solution is stored in <tt>debts</tt>
	 * but the debts needs to be added to debtors and creditors.
	 * 
	 * @param debtors		list of current debtors with unsettled debts
	 * @param creditors		list of current creditors with unsettled debts
	 */
	private void search(List<Person> debtors, List<Person> creditors) {
		logger.log(Level.FINER, "\nDebtors: {0}\nCreditors {1}", new Object[]{debtors, creditors});
		
		for (Person debtor : debtors) {
			for (Person creditor : creditors) {
				logger.log(Level.FINER, "Matching debtor {0} and creditor {1}", new Object[]{debtor, creditor});
				
				double totalToPay = Math.abs(debtor.getBalance());
				double totalToGet = Math.abs(creditor.getBalance());
				Debt debt = EntityManager.createDebt(debtor, creditor);
				currentDebts.add(debt);
				
				List<Person> nextDebtors = new ArrayList<Person>(debtors);
				List<Person> nextCreditors = new ArrayList<Person>(creditors);
				if (totalToGet > totalToPay) {
					debt.setValue(totalToPay);;
					nextDebtors.remove(debtor);
				} else if (totalToGet < totalToPay) {
					debt.setValue(totalToGet);
					nextCreditors.remove(creditor);
				} else {
					debt.setValue(totalToGet);
					nextDebtors.remove(debtor);
					nextCreditors.remove(creditor);
				}
				
				// Recursion step
				if (nextDebtors.size() > 0 || nextCreditors.size() > 0) {
					search(nextDebtors, nextCreditors);
				} else if (nextDebtors.size() == 0 && nextCreditors.size() == 0) {
					if (debts == null || currentDebts.size() < debts.size()) {
						debts = new ArrayList<Debt>(currentDebts);
						logger.log(Level.FINE, "Found better solution, now {0} debts:\n{1}", new Object[]{debts.size(), debts});
					} else {
						logger.log(Level.FINE, "Branch finished without improving solution: {0} debts", currentDebts.size());
					}
				}/* else {
					throw new RuntimeException("Only debtors or only creditors left");
				}*/
				
				// For the next recursion step, we need to cancel the changes did in the previous step 
				currentDebts.remove(debt);
				debtor.removeTransaction(debt);
				
			}
		}
		
	}

}
